﻿// Principia
// Copyright (C) 2008 Blake Hegerle
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Principia.Core
{
    public class Graph
    {
        public static IEnumerable<T> Reachable<T>(T Start, Func<T, IEnumerable<T>> EdgeFunction)
        {
            return Reachable(Start.Singleton(), EdgeFunction);
        }

        public static IEnumerable<T> Reachable<T>(IEnumerable<T> StartingSubGraph, Func<T, IEnumerable<T>> EdgeFunction)
        {
            // This is the object we'll use to collect the reachable subgraph
            var VisitedSet = new Set<T>();

            // These are the most-recently discovered nodes - starting with StartingSubGraph
            var Step = new List<T>();
            Step.AddRange(StartingSubGraph);

            // While we keep discovering nodes
            while (Step.Count > 0)
            {
                var NextStep = new List<T>();

                foreach (var Node in Step)
                {
                    VisitedSet.Add(Node);

                    foreach (var LinkedNode in EdgeFunction(Node))
                        if (VisitedSet.Contains(LinkedNode) == false)
                            NextStep.Add(LinkedNode);
                }

                Step = NextStep;
            }

            return VisitedSet;
        }

        public static bool Cyclic<T>(IEnumerable<T> StartingSubGraph, Func<T, IEnumerable<T>> EdgeFunction)
        {
            return (StartingSubGraph.Count() != 0)
                   && (StartingSubGraph.All(S => CyclicNode(S, EdgeFunction)));
        }

        public static bool CyclicNode<T>(T S, Func<T, IEnumerable<T>> EdgeFunction)
        {
            return Cyclic(S, EdgeFunction, new Set<T>());
        }

        private static bool Cyclic<T>(T node, Func<T, IEnumerable<T>> EdgeFunction, ICollection<T> Visited)
        {
            if (Visited.Contains(node))
                return true;

            Visited.Add(node);

            foreach (var c in EdgeFunction(node))
                if (Cyclic(c, EdgeFunction, Visited))
                    return true;

            Visited.Remove(node);

            return false;
        }
    }
}